package hashdemo;

import java.util.*;

/**
 * @author tongchen
 * @create 2022-11-20 19:01
 */
public class ExerLeetCode {

    public List<String> topKFrequent(String[] words, int k) {
        //建立一个新的顺序表
        ArrayList<String> arraylist=new ArrayList<>();
        //校验数组的合法性
        if(words==null||words.length==0){
            return arraylist;
        }
        //建立map统计次数
        Map<String,Integer> map=new HashMap<>();
        for(int i=0;i<words.length;++i){
            int num=map.getOrDefault(words[i],0);
            map.put(words[i],num+1);
        }
        //将map进行转化
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        //建立优先级队列
        PriorityQueue<Map.Entry<String,Integer>>priorityQueue=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue()==o2.getValue()){
                   return o2.getKey().compareTo(o1.getKey());
                }
                else{
                    return o1.getValue()-o2.getValue();
                }
            }
        });
//加入优先级队列
        for (Map.Entry<String,Integer> entry:entries) {
            priorityQueue.offer(entry);
            // 2. 队列大小大于K时，出队堆顶元素(这个元素是按照比较规则排好序的)
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }
        //加入并反转
        // 4. 把优先级队列中的元素依次加入到List中
        while (!priorityQueue.isEmpty()) {
            arraylist.add(priorityQueue.poll().getKey());
        }
        // 5. 解决返转问题
        Collections.reverse(arraylist);
        // 6. 返回
        return arraylist;
        }
    }

